package com.github.yangyishe;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 763. 划分字母区间
 * https://leetcode.cn/problems/partition-labels/description/?envType=study-plan-v2&envId=top-100-liked
 * todo 时间复杂度并不高，但实际执行速度较慢，可能是用了较多的工具类导致的
 *
 * 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
 *
 * 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
 *
 * 返回一个表示每个字符串片段的长度的列表。
 *
 *
 *
 * 示例 1：
 * 输入：s = "ababcbacadefegdehijhklij"
 * 输出：[9,7,8]
 * 解释：
 * 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
 * 每个字母最多出现在一个片段中。
 * 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
 * 示例 2：
 *
 * 输入：s = "eccbbbbdec"
 * 输出：[10]
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 500
 * s 仅由小写英文字母组成
 */
public class Problem763 {
    public static void main(String[] args) {
        String s="eccbbbbdec";

        Problem763 problem763 = new Problem763();
        List<Integer> partitionLabels = problem763.partitionLabels(s);
        System.out.println("partitionLabels = " + partitionLabels);
    }

    public static class Zone{
        char c;
        int start;
        int end;

        public Zone(char c, int start, int end) {
            this.c = c;
            this.start = start;
            this.end = end;
        }
    }

    /**
     * 思路：
     * 如果要人手动去算，从第一个字符开始start1，先找该字符在最后的位置end1，则[start1,end1]构建的字符串必定是在一起的。
     * 可以将字符串，整理为每个字符对应最早和最晚的边界索引。
     * 如a:[0,9];b:[1,7];c:[4,6];e:[10,15];...
     * 之后逐个遍历这些边界，并创建新的区间集合；并维护一个空白区间集合。
     * 如果新字符区间的边界，在空白区间内部，则创建一个新的边界；
     * 如果新字符区间的边界，没有在空白区间内部，则必然在某个已构建的区间内部或之间，扩展之；
     *
     * @param s
     * @return
     */
    public List<Integer> partitionLabels(String s) {
        Map<Character,Zone> char2ZoneMap=new HashMap<>();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(char2ZoneMap.get(c)==null){
                char2ZoneMap.put(c,new Zone(c,i,i));
            }else{
                char2ZoneMap.get(c).end=i;
            }
        }

        // 对已收集集合进行排序
        List<Zone> zoneList = char2ZoneMap.values().stream().sorted(Comparator.comparingInt(o -> o.start)).collect(Collectors.toList());

        // 遍历区域
        int startIndex=-1;
        int endIndex=-1;
        List<Integer> resultList=new ArrayList<>();
        for(Zone zone:zoneList){
            if(startIndex==-1){
                startIndex=zone.start;
                endIndex=zone.end;
            }else{
                if(zone.start<endIndex){
                    endIndex=Math.max(endIndex,zone.end);
                }else{
                    resultList.add(endIndex-startIndex+1);
                    startIndex=zone.start;
                    endIndex=zone.end;
                }

            }
        }
        resultList.add(endIndex-startIndex+1);

        return resultList;
    }
}
